package 动态规划.背包And分组And切割问题系列;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/8 16:21
 */
public class 数字切割游戏 {
    /*
     这道题 来自 lc 网友的提问：  这个 题 跟 lc2698 这道题   完全是一个类型的

     给出一个数字 n （  n ∈ [1, 10 ^ 10] ）
     求把数字 n 切割, 所有切割方案的 切割 和!

     eg:  输入 : n = 125
     有三种切割方案:
      ①: 1 + 2 + 5 = 8
      ②: 12 + 5 = 17
      ③: 125 = 125
      ④: 1 + 25 = 26
      所以 和 位  ① + ② + ③ + ④ = 176
     */



    // 错误的
    /*
     就拿上面的 例子举例,
     问题出在下面这段代码上面!
     ans += recursion(i,n) + Integer.parseInt(n.substring(index,i));

    - 如果按照上面这段代码的方式写的话, 1, 2,5 和 1,25 这两种切割方案, 你会发现 1 只被 累加了一次,导致 求和 不对!
    所以这种回溯是错误的!
     */
    public int recursion(int index,String n){
        if(index == n.length()){
            return 0;
        }
        int ans = 0;
        for(int i = index + 1;i <= n.length();i++){

            ans += recursion(i,n) + Integer.parseInt(n.substring(index,i));
        }
        return ans;
    }

    // 正确的
    int sum = 0;
    public void recursion(int index,String n ,int cur){
        if(index == n.length()){
            sum += cur;
            return ;
        }
        int ans = 0;
        for(int i = index + 1;i <= n.length();i++){
//            ans += recursion(i,n) + Integer.parseInt(n.substring(index,i));
            recursion(i, n,cur + Integer.parseInt(n.substring(index,i)));
        }
//        return ans;
    }



        long find(String s,long sum,int idx){
        if(idx==s.length()){
            return sum;
        }
        long ans=0;
        for(int i=idx+1;i<=s.length();i++){
            ans+=find(s,sum+Long.parseLong(s.substring(idx,i)),i);
        }
        return ans;
    }


    /*
     下面这种 缓存, 就是错误的, 我算是 明白了,为什么 f()函数 参数的变量的个数,决定了 缓存表的维度!

     - 这里只想用 idx 做一维 缓存 dp[index] :表示的 是 以index 开头到 结尾, 所有切割方案的总和
     好像一个很不错的 缓存!
     举个例子就明白了!
     eg:  1257
     假设 一次切割 为 :  1, 2 ,57 这种切割 方案 已经 把 57 所有的 所有的切割方案都算过了 假设为 x, 缓存起来 dp[2] = x
     所以 在  12 ,57 这次切割的时候,我们就不用在切割 57, 直接从 dp取值,  **想法是美好的!**
     但是 问题,在于 1,2,57 这种的前置 sum = 3 , 而 12,57 的前置 sum = 12, 根本就不对
     - 或许说 dp函数的定义 就是错误的,所以这道题 ,只能回溯, 没办法 使用缓存!

     - 如果使用二维 dp 的话, 你会发现 sum 变量的取值范围 ,根本就确定不了!, 没法玩!
     */

        long find(String s,long sum,int idx,Long dp[]){
        if(idx==s.length()){
            return sum;
        }
        if(dp[idx] != null){
            return dp[idx];
        }
        long ans=0;
        for(int i=idx+1;i<=s.length();i++){
            ans+=find(s,sum+Long.parseLong(s.substring(idx,i)),i,dp);
        }
        return dp[idx] = ans;
    }


    @Test
    public void test(){
        long n = 1398872838902839908l;
//        double num = (long)Math.pow(10,10);
//        System.out.println(num + "");
//        System.out.println(recursion(0,String.valueOf(n)));
//        recursion(0,n + "",0);
//        System.out.println(sum);
        long l = System.currentTimeMillis();
        System.out.println(find(n + "",0,0));
        long l1 = System.currentTimeMillis();
//        System.out.println("hskgh");
        System.out.println(l1 - l);
    }
}
